package leetcode.editor.cn.dsa15_stackAndGA;
// 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
// 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
//
// 它是一个空字符串，或者 
// 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者 
// 它可以被写作 (A)，其中 A 是有效字符串。 
//
// 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。 
//
// 示例 1： 
// 输入："())"
// 输出：1
//
// 示例 2： 
// 输入："((("
// 输出：3
// 
// 示例 3：
// 输入："()"
// 输出：0
// 
// 示例 4：
// 输入："()))(("
// 输出：4
//
// 提示：
// S.length <= 1000
// S 只包含 '(' 和 ')' 字符。 
//
// Related Topics 栈 贪心算法 
// 👍 72 👎 0

public class MinimumAddToMakeParenthesesValid921 {
    public static void main(String[] args) {
        Solution solution = new MinimumAddToMakeParenthesesValid921().new Solution();
        System.out.println(solution.minAddToMakeValid("()()")); //0
        System.out.println(solution.minAddToMakeValid("())")); //1
        System.out.println(solution.minAddToMakeValid("(((")); //3
        System.out.println(solution.minAddToMakeValid("()))((")); //4
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minAddToMakeValid(String S) {
            // 使用计数器
            int leftCount = 0, rightCount = 0;
            char[] chars = S.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                // 当前字符为右括号，看看是否有左括号，有则左括号个数-1
                if (c == ')' && leftCount != 0) leftCount--;
                // 否则对相应的括号进行计数
                else if (c == ')') rightCount++;
                else leftCount++;
            }
            return leftCount + rightCount;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}